//由于采用了插入排序的排序算法，未能在规定时间内完成运行
//使用logN排序算法即可
class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		if (intervals.size() < 2) return intervals;
		sort(intervals);
		vector<vector<int>> ret;
		ret.push_back(intervals[0]);
		for (int i = 1; i <= intervals.size() - 1; i++) {
			if (intervals[i][0] > ret[ret.size() - 1][1]) {
				ret.push_back(intervals[i]);
			}
			else {
				ret[ret.size() - 1][1] = ret[ret.size() - 1][1] > intervals[i][1] ?
					ret[ret.size() - 1][1] : intervals[i][1];
			}
		}
		return ret;
	}
private:
	void sort(vector<vector<int>>& intervals) {
		int i, j;
		for (i = 1; i <= intervals.size() - 1; i++) {
			vector<int> benchMark = intervals[i];
			for (j = i - 1; j >= 0; j--) {
				if (intervals[j][0] > benchMark[0]) {
					intervals[j + 1] = intervals[j];
				}
				else {
					break;
				}
			}
			intervals[j + 1] = benchMark;
		}
	}
};